
public class quickSort{

	/**
	 * 快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为：
	 * 从序列中挑出一个元素，作为"基准"(pivot).
	 * 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），
	 * 这个称为分区(partition)操作。
	 * 对每个分区递归地进行步骤1~3，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。
	 *
	 * 分类：内部比较排序
	 * 数据结构：数组
	 * 最差时间复杂度：每次选取的基准都是最大的元素，导致每次只划分除了一个子序列，需要进行n-1次划分
	 * 才能结束递归，时间复杂度为O(n^2)
	 * 最优时间复杂度：每次选取的基准都能使划分均匀，只要logn次划分就能结束递归，时间复杂度为O(nlogn)
	 * 所需辅助空间：O(logn)~O(n),主要是递归造成的栈空间的使用
	 * 稳定性：不稳定
	 * 
	 * [sort description]: 快速排序，主要是利用递归算法
	 * @param array [description]
	 */
	public static void sort(int [] array){
		int len = array.length;
		quickSort(array,0,len-1);
	}

 	/**
 	 * 通过一次分区，找到数组基准的索引位置
 	 * 然后递归对索引左边的数组和索引右边的数组进行快排
 	 * [quickSort description]:对数组进行快排，数组的初始索引为left，最后一个元素的索引为right
 	 * @param array [description]
 	 * @param left  [description]
 	 * @param right [description]
 	 */
	private static void quickSort(int [] array, int left, int right){
		int pivotIndex;
		if(left < right){
			pivotIndex = partition(array,left,right);
			quickSort(array,left,pivotIndex-1);
			quickSort(array,pivotIndex+1,right);
		}
	}

	/**
	 * [partition description]:分区函数，定数组的第一个元素为基准，然后将小于基准的元素全部放在基准左边，
	 * 大于基准的元素全部放在基准右边，然后返回基准的索引值。
	 * @param  array [description]
	 * @param  left  [description]
	 * @param  right [description]
	 * @return       [description]
	 */
	private static int partition(int [] array, int left,int right){
		int pivot = array[left];
		while(left < right){
			while(left < right && array[right] >= pivot){
				right --;
			}
			array[left] = array[right];
			while(left < right && array[left] <= pivot){
				left ++;
			}
			array[right] = array[left];
		}
		array[left] = pivot;
		return left;
	}

	public static void main(String [] args){
		int [] array = {1,3,1,4,1,5,1,6};
		sort(array);
		for(int i=0;i<array.length;i++){
			System.out.print(array[i]+" ");
		}
	}
}